package pro.softzhang.algo.lc500;

import java.util.Random;

/**
 *
 */
public class LC528_RandomPickWithWeight {
    public static void main(String[] args) {
        int[] w = {};
        int idx = new LC528_Solution(w).pickIndex();
        System.out.println(idx);
    }
}

class LC528_Solution {
    private int[] sums;
    private int total;
    private Random random = new Random();

    public LC528_Solution(int[] w) {
        sums = new int[w.length];
        for (int i = 0; i < w.length; i++) {
            total += w[i];
            sums[i] = total;
        }
    }

    public int pickIndex() {
        int p = new Random().nextInt(total);
        int left = 0, right = sums.length;
        while (left <= right) {
            int middle = (left + right) / 2;
            if(sums[middle] > p) {
                if(middle == 0 || sums[middle - 1] <= p) {
                    return middle;
                }
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return -1;
    }
}
